#include "../comm.h"
class Skiplist {
private:    struct node
    {
        int _val;
        vector<node*> _next;
    public:
        node(int level, int val = 0)
            :_next(level,nullptr), _val(val) {} 
    };
private:
    static const int maxLevel = 32;
    static constexpr double p = 0.5;
    node* _head = nullptr; 
    int _nowLevel = 0;
private:
    // 获取一个随机的层数
    int randomLevel()
    {
        int l = 1;
        while(rand() >= p * RAND_MAX)
            ++l;
        return l;
    }
    // 获得一个给定值所在位置的前面所有结点
    vector<node*> getPrevNode(int val)
    {
        vector<node*> prev(maxLevel, _head);
        node* cur = _head;
        int level = _nowLevel - 1;
        while(level >= 0)
        {
            node* next = cur->_next[level];
            if(next && next->_val < val)
                cur = next;
            else  // 另外的可能就是结点不存在或者下一个结点的val大于当前val
                  // 那么level就要向下走，并且保存当前结点
            {
                prev[level] = cur;
                level--;
            }
        }
        return prev;
    }
public:
    Skiplist() {
        _head = new node(maxLevel, 0);
        srand(time(nullptr));
    }
    
    bool search(int target) {
        auto prev = getPrevNode(target);
        // for(int i = 5; i >= 0; --i)
            // cout << prev[i]->_val << ' ';
        // cout << endl;
        node* cur = prev[0]->_next[0];
        if(cur && cur->_val == target)
            return true;
        return false;
    }
    
    void add(int num) {
        auto prev = getPrevNode(num);
        int level = randomLevel();
        // cout << level << endl;
        _nowLevel = max(_nowLevel, level);
        node* newNode = new node(level, num);
        for(int i = level - 1; i >= 0; --i)
        {
            newNode->_next[i] = prev[i]->_next[i];
            prev[i]->_next[i] = newNode;
        }
        // print();
    }
    void print()
    {
        node* cur = _head->_next[0];
        while(cur)
        {
            cout << cur->_val << ":" << cur->_next.size() << ' ';
            cur = cur->_next[0];
        }
        cout << endl;
    }
    bool erase(int num) {
        if(!search(num)) return false;
        auto prev = getPrevNode(num);
        node* cur = prev[0]->_next[0];
        auto& next = cur->_next;
        for(int i = next.size() - 1; i >= 0; --i)
            prev[i]->_next[i] = next[i];
        delete cur;
        return true;
    }
};

/**
 * Your Skiplist object will be instantiated and called as such:
 * Skiplist* obj = new Skiplist();
 * bool param_1 = obj->search(target);
 * obj->add(num);
 * bool param_3 = obj->erase(num);
 */